

\chapter{Dependency Parsing}
\label{ch03dep}





\section{Representation}

A dependency graph G=(V,A) is a labeled directed graph (digraph) in the standard graph-theoretic sense and consists of nodes, V, and arcs, A, such that for an MRL sentence \(x=x_1...x_n\) with morpheme set MS and label set R the following holds:
VMS

Let \(R={r_1,...,r_m}\) be a finite set of possible dependency relation labels that can hold between any two morphemes in a sentence. A relation  \(r\in R\) is  called an arc label.


Let \(\mcr={r_1,...,r_m}\) be a finite set of possible dependency relation labels that can hold between any two morphemes in a sentence. A relation of type \(r\in R\) is additionally called an arc label.

A dependency graph G=(V,A)is a labeled directed graph (digraph) in the standard graph-theoretic sense and consists of nodes, V, and arcs, A, such that for an MRL sentence S=x1...xn with morpheme set MS and label set R the following holds:
VMS
AVRV
if (si,r,sj)A then (si,r',sj)Afor all r' r

A well formed dependency graph G=(V,A) for an input sentence Sand dependency relation set R is any dependency graph that is a directed tree originating out of node s0 and has spanning node set V=MS. We call such dependency graphs dependency trees.

Given a set R of dependency types, a configuration for a sentence S=x1...xnand morpheme set MSis a 5-tuple:
c=(,s,x,,A) where:
is a stack of morphemes siMS
sis a queue of morphemes siMS
(x,s):si,sjs ; we constrain sto only contain morphemes of the same word
xis a queue of tokens xiS
A is a set of dependency arcs (si,r,sj)MSRMS 
 is a mapping {(xi,si1...sij)|wiS,si1...sijMA(xi)}

For any sentence S=x1...xn,
the initial configuration  is of the form c0(S)is ([s0],[]s,[x1,...,xn]x,{}A,{})
a terminal configuration is of the form  cfinal(S) =([so],[]s,[]x,A,)for any ,Aand .

Morph. Arc-Standard Deterministic Transition Table 
Transition
Initials
Configuration after transition
Cond.
LEFT-ARCr
LAr
(|si,sj|s,x,A,)(|sj,s,x,A{(sj,r,si)},)
i0
RIGHT-ARCr
RAr
(|si,sj|s,x,A,)(,si|s,x,A{(si,r,sj)},)
(x,s):
si,sjs
SHIFT
SH
(,si|s,x,A,)(|si,s,x,A{(si,r,sj)},)


MORPHOLOGICAL DISAMBIGUATIONs
MDs
(,s,xi|x,A,)
(,s1|s2|...|sn|s,x,A,(wi,s1...sn))
s1...snMA(xi)
s=[]

Oracle:
Let Gd=(Vd,Ad) be a dependency tree for a sentence Sd with mapping S
o(c=(,s,x,A,))=
Transition
Choice
Condition
LEFT-ARCr


if (s[0],r,[0])Ad
RIGHT-ARCr


if ([0],r,s[0])Adand, for all s,r',
if (s[0],r',s)Adthen (s[0],r',s)A
SHIFT


s[]
MDs
s=s1... sn
(x,s1... sn)S
s=[]

\section{Transition-Based Modeling}

 
\subsection{Decoding}

\subsection{Learning}

\subsection{Evaluation}


\section{Graph-Based Modeling}

%\subsection{Representation}

 
\subsection{Decoding}

\subsection{Learning}

\subsection{Evaluation}


\section{Coping with Non-Projective Dependencies}

\section{Summary and Further Reading}
